/*
 * @Author: wwssaabb
 * @Date: 2021-11-30 10:47:55
 * @LastEditTime: 2021-12-02 11:14:40
 * @FilePath: \handwritten-code\algorithm\0~n-1中缺失的位置.js
 */
/* 
一个长度为n - 1 的递增排序数组中的所有数字都是唯一的， 并且每个数字都在范围0～ n - 1 之内。 在范围0～ n - 1 内的n个数字中有且只有一个数字不在该数组中， 请找出这个数字。

示例 1:

  输入: [0, 1, 3]
输出: 2
示例 2:

  输入: [0, 1, 2, 3, 4, 5, 6, 7, 9]
输出: 8

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
*/

//二分法O(logn) 空间:O(1)
var missingNumber = function (nums) {
  let left = 0,
    right = nums.length - 1
  if (!nums.length) return -1
  if (nums[0] !== 0) return 0
  while (left <= right) {
    let mid = (left + right) >> 1
    if (nums[mid] === mid) {
      if (nums[mid + 1] - nums[mid] === 2 || !nums[mid + 1]) return nums[mid] + 1
      left = mid + 1
    } else if (nums[mid] === mid + 1) {
      if (nums[mid] - nums[mid - 1] === 2 || !nums[mid - 1]) return nums[mid] - 1
      right = mid
    }
  }
  return -1
};

// console.log(missingNumber([0]))
// console.log(missingNumber([0, 1]))
// console.log(missingNumber([0, 1, 3]))
// console.log(missingNumber([0, 1, 3, 4]))
// console.log(missingNumber([0, 1, 2, 3, 4, 5]))
console.log(missingNumber([
  0, 1, 3, 4, 5, 6, 7, 8, 9
]))
// console.log(missingNumber([0, 1, 2, 3, 4, 5, 6, 7, 9]))
// console.log(missingNumber([0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]))